import os
import sys
from typing import Optional

# Add the parent directory to the Python path
sys.path.append(os.path.dirname(os.path.dirname(os.path.abspath(__file__))))
from mypackage import TreeNode


class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        stack, inorder = [], float('-inf')
        while stack or root:
            while root:
                stack.append(root)
                root = root .left
            root = stack.pop()
            if root.val <= inorder:
                return False
            inorder = root.val
            root = root.right
        return True

    def isValidBST1(self, root: Optional[TreeNode]) -> bool:
        def recurse(node, lower = float('-inf'), upper = float('inf')) -> bool:
            if not node:
                return True
            val = node.val
            if val <= lower or val >= upper:
                return False
            if not recurse(node.right, val, upper):
                return False
            if not recurse(node.left, lower, val):
                return False
            return True
        return recurse(root)
    
    """
    方法：isValidBST 验证二叉搜索树
    
    通过中序遍历检查二叉树是否为有效的二叉搜索树。
    在二叉搜索树中，中序遍历得到的值序列应该是严格递增的。
    
    Args:
        root: Optional[TreeNode] - 二叉树的根节点
    
    Returns:
        bool: 如果是有效的二叉搜索树则返回True，否则返回False
    
    Time: O(n) - 其中n是二叉树的节点数，每个节点只被访问一次
    
    Space: O(h) - 其中h是二叉树的高度，用于存储递归调用栈
    """
    
    def test_isValidBST(self):
        # 创建测试用例: [4,2,5,1,3,null,6]
        root = TreeNode(4)
        root.left = TreeNode(2)
        root.right = TreeNode(5)
        root.left.left = TreeNode(1)
        root.left.right = TreeNode(3)
        root.right.right = TreeNode(6)
        
        # 调用方法
        result = self.isValidBST(root)
        expected = True
        
        # 输出结果
        print(f"测试 isValidBST:")
        print(f"输入: [4,2,5,1,3,null,6]")
        print(f"结果: {result}")
        print(f"预期: {expected}")
        print(f"测试{'通过' if result == expected else '失败'}")
        
        # 创建一个非有效BST的测试用例: [5,1,4,null,null,3,6]
        invalid_root = TreeNode(5)
        invalid_root.left = TreeNode(1)
        invalid_root.right = TreeNode(4)
        invalid_root.right.left = TreeNode(3)
        invalid_root.right.right = TreeNode(6)
        
        # 调用方法
        result2 = self.isValidBST(invalid_root)
        expected2 = False
        
        # 输出结果
        print(f"\n测试 isValidBST:")
        print(f"输入: [5,1,4,null,null,3,6]")
        print(f"结果: {result2}")
        print(f"预期: {expected2}")
        print(f"测试{'通过' if result2 == expected2 else '失败'}")


if __name__ == "__main__":
    solution = Solution()
    solution.test_isValidBST()